<!DOCTYPE html>
<html lang="zh-CN">

<!-- Head tag -->
<head>
  <meta charset="utf-8">
  <meta http-equiv="X-UA-Compatible" content="IE=edge">
  
  <meta name="baidu-site-verification" content="undefined" />
  <meta name="google-site-verification" content="undefined" />
  <meta name="msvalidate.01" content="undefined" />
  <meta name="360-site-verification" content="undefined" />
  <meta name="viewport" content="width=device-width, initial-scale=1">
  <!-- if page has tags, then add tags to keyword -->
  
  
  <meta name="keywords" content=",Golang,Golang源码,">
  <!-- page.description has higher priority -->
  <meta name="description" content="列出sort包实现的各种排序函数">
  <link rel="shortcut icon" href="/blog/img/logo.webp">
  <title>
    
    Go源码学习 sort包 | Evrn
    
  </title>

  <link rel="canonical" href="/blog/post/go-learn-lib-sorts.html">
  
<link rel="stylesheet" href="/blog/css/reset.css">

  
<link rel="stylesheet" href="/blog/css/layout.css">

  
<link rel="stylesheet" href="/blog/css/markdown.css">

  <!-- Pygments Highlight CSS -->
  
<link rel="stylesheet" href="/blog/css/highlight.css">

  
<link rel="stylesheet" href="/blog/css/geektutu.css">

  <!-- global function -->
  <script>
    window.globalAddScript = function (url, onload, onerror) {
      var s = document.createElement('script');
      s.src = url;
      onload && (s.onload = onload);
      onerror && (s.onerror = onerror);
      document.body.appendChild(s);
    }
    window.globalAddCss = function (url) {
      var s = document.createElement('link');
      s.rel = 'stylesheet';
      s.href = url;
      document.body.appendChild(s);
    }
    window.getPosition = function (ele) {
      var x = 0, y = 0;
      while (ele) {
        x += (ele.offsetLeft - ele.scrollLeft + ele.clientLeft);
        y += (ele.offsetTop - ele.scrollTop + ele.clientTop);
        ele = ele.offsetParent;
      }
      return { x: x, y: y };
    }
    window.getDom = function (str) { return document.querySelector(str) }
  </script>
  <!-- google ad -->
  
<meta name="generator" content="Hexo 4.2.0"></head>

<body>
    <header class="gkt-header col-xs-12 padding-0">
    <div id="gkt-nav" class="gkt-header-container">
        <a href="/blog/" class="gkt-header-title float-left">
            <img class="float-left" src="/blog/img/logo.webp" alt="">
            <span>Evrn</span>
        </a>
        <nav class="gkt-header-nav text-right">
            <ul>
                <li><a class="hidden-xs" href="/blog/">主页</a></li>
                <li><a href="/blog/series/">专题</a></li>
                <li><a href="/blog/archives/">归档</a></li>
                <li><a href="/blog/post/link.html">友链</a></li>
                <li><a href="/blog/post/about.html">留言</a></li>
            </ul>
        </nav>
    </div>
    <div id="gkt-cate-nav" class="gkt-header-container hidden-xs">
        
        <nav class="gkt-header-nav float-left">
            <ul>
                
                
                <li class="gkt-cate-name float-left active">
                    <a class="float-left" href="/blog/post/go-learn-interface.html">Golang学习</a>
                    
                </li>
                
                <li class="gkt-cate-name float-left ">
                    <a class="float-left" href="/blog/post/go-asm-indroduce.html">Golang汇编</a>
                    
                </li>
                
                <li class="gkt-cate-name float-left ">
                    <a class="float-left" href="/blog/post/tcp-three-way-handshake.html">基础</a>
                    
                </li>
                
                <li class="gkt-cate-name float-left ">
                    <a class="float-left" href="/blog/post/go-how-to-build.html">Golang底层</a>
                    
                </li>
                
                <li class="gkt-cate-name float-left ">
                    <a class="float-left" href="/blog/post/mysql-index-use.html">MySQL</a>
                    
                </li>
                
            </ul>
        </nav>
    </div>
</header>
<div style="height: 44px"></div>
<div class="hidden-xs" style="height: 44px"></div>
<script>
    (function () {
        window.addEventListener('scroll', function () {
            if (window.innerWidth < 768) {
                return;
            }
            var nav = document.querySelector('#gkt-nav');
            var scrollTop = document.documentElement.scrollTop || document.body.scrollTop;
            scrollTop > 50 && (nav.classList.add('hide'));
            scrollTop <= 50 && (nav.classList.remove('hide'));
        });
        var cateNavs = document.querySelectorAll('#gkt-cate-nav>nav>ul>li');
        [].slice.call(cateNavs).forEach(function (item) {
            var sub = item.querySelector('.gkt-sub-cate');
            if (!sub) return;
            item.addEventListener('mouseenter', function (e) { sub.style.display = 'block'; }, false);
            item.addEventListener('mouseleave', function (e) { sub.style.display = 'none'; }, false);
        })
    })();
</script>
    <!-- Main Content -->
    <div class="main-container">
        <!-- Main Content -->
<main class="col-xs-12 padding-0 markdown-it">
    <!-- Post Container -->
    
    
    <!-- Post Content -->
<div class="float-left post-container box-shadow">
    <div class="u-arrow-wrapper hidden-xs">
        
        <a class="float-left" href="/blog/post/mysql-optimize-explain.html"><i class="u-arrow-left"></i></a>
        
        
    </div>
    <article class="col-xs-12">
        <h1> Go源码学习 sort包 </h1>

        

        
        <div class="hidden-lg hidden-md series_links">
            <p> <strong> Golang学习系列文章链接：</strong></p>
            <ul>
                
                <li>
                    <a href="/blog/post/go-learn-interface.html">Go学习 接口和类型断言</a>
                    <span class="post-item-date">(Jan 21, 2019)</span>
                </li>
                
                <li>
                    <a href="/blog/post/go-learn-lib-sorts.html">Go源码学习 sort包</a>
                    <span class="post-item-date">(Mar 11, 2020)</span>
                </li>
                
            </ul>
        </div>
        
        
        
        <p>go自带的sort包，实现了各种常用的排序算法，足以应付大部分需求</p>
<h2 id="接口"><a href="#接口" class="headerlink" title="接口"></a>接口</h2><p>sort包通过接口实现算法的一般性应用，我们自定义的数组类型只要实现了这个接口都可以直接用sort解决</p>
<figure class="highlight go"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">//只要实现了这个接口的数组就可以用这里的排序方法来排序</span></span><br><span class="line"><span class="keyword">type</span> Interface <span class="keyword">interface</span> &#123;</span><br><span class="line">	<span class="comment">// 返回数组大小</span></span><br><span class="line">	Len() <span class="keyword">int</span></span><br><span class="line">	<span class="comment">// 返回判断i索引 &lt; j索引</span></span><br><span class="line">	Less(i, j <span class="keyword">int</span>) <span class="keyword">bool</span></span><br><span class="line">	<span class="comment">// 交换i,j的位置</span></span><br><span class="line">	Swap(i, j <span class="keyword">int</span>)</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>sort包内部对几个基本类型<code>float64</code>,<code>string</code>,<code>int</code>实现了这个接口，以[]int为例</p>
<figure class="highlight go"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">// int数组实现以上的接口</span></span><br><span class="line"><span class="keyword">type</span> IntSlice []<span class="keyword">int</span></span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">func</span> <span class="params">(p IntSlice)</span> <span class="title">Len</span><span class="params">()</span> <span class="title">int</span></span>           &#123; <span class="keyword">return</span> <span class="built_in">len</span>(p) &#125;</span><br><span class="line"><span class="function"><span class="keyword">func</span> <span class="params">(p IntSlice)</span> <span class="title">Less</span><span class="params">(i, j <span class="keyword">int</span>)</span> <span class="title">bool</span></span> &#123; <span class="keyword">return</span> p[i] &lt; p[j] &#125;</span><br><span class="line"><span class="function"><span class="keyword">func</span> <span class="params">(p IntSlice)</span> <span class="title">Swap</span><span class="params">(i, j <span class="keyword">int</span>)</span></span>      &#123; p[i], p[j] = p[j], p[i] &#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">//使用的时候调用Sort()就可以</span></span><br><span class="line"><span class="function"><span class="keyword">func</span> <span class="title">Ints</span><span class="params">(a []<span class="keyword">int</span>)</span></span> &#123; Sort(IntSlice(a)) &#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">func</span> <span class="title">Sort</span><span class="params">(data Interface)</span></span> &#123;</span><br><span class="line">	n := data.Len()</span><br><span class="line">	quickSort(data, <span class="number">0</span>, n, maxDepth(n))</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>



<h2 id="堆排序"><a href="#堆排序" class="headerlink" title="堆排序"></a>堆排序</h2><p>sort包使用下沉法构造最大堆，交换的时候根元素与子元素交换，向下沉<br>最大堆，父节点比左右儿子都小，左右儿子之间大小不比较<br>父结点比最大儿子节点都大就结束构造，否则跟最大儿子交换<br>默认原最大儿子的分支已经构建好最大堆，因此交换后该分支需要重新构造，保持父结点最大的性质<br>对索引lo到hi范围的数组实现最小堆算法<br>树下标从0开始左儿子2i+1，下标从1开始左儿子2i，这里是下标从0开始</p>
<figure class="highlight go"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">// 对data数组索引从a-b范围的数据进行堆排序</span></span><br><span class="line"><span class="function"><span class="keyword">func</span> <span class="title">heapSort</span><span class="params">(data Interface, a, b <span class="keyword">int</span>)</span></span> &#123;</span><br><span class="line">	first := a</span><br><span class="line">	lo := <span class="number">0</span></span><br><span class="line">	hi := b - a</span><br><span class="line"></span><br><span class="line">	<span class="comment">// 构建大顶堆</span></span><br><span class="line">	<span class="keyword">for</span> i := (hi - <span class="number">1</span>) / <span class="number">2</span>; i &gt;= <span class="number">0</span>; i-- &#123;</span><br><span class="line">		siftDown(data, i, hi, first)</span><br><span class="line">	&#125;</span><br><span class="line"></span><br><span class="line">	<span class="keyword">for</span> i := hi - <span class="number">1</span>; i &gt;= <span class="number">0</span>; i-- &#123;</span><br><span class="line">                <span class="comment">//first就是根节点，也就是最大的数，每次取剩余最大的，</span></span><br><span class="line">                <span class="comment">//从后往前放到序列中合适的位置</span></span><br><span class="line">		data.Swap(first, first+i)   </span><br><span class="line">                <span class="comment">//未排序数又放到堆中因此要重新构造</span></span><br><span class="line">		siftDown(data, lo, i, first) </span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br><span class="line"><span class="comment">// lo,hi并不是真实的索引，只是相对于first的索引</span></span><br><span class="line"><span class="function"><span class="keyword">func</span> <span class="title">siftDown</span><span class="params">(data Interface, lo, hi, first <span class="keyword">int</span>)</span></span> &#123;</span><br><span class="line">	root := lo</span><br><span class="line">	<span class="keyword">for</span> &#123;</span><br><span class="line">		child := <span class="number">2</span>*root + <span class="number">1</span> <span class="comment">// 左儿子</span></span><br><span class="line">		<span class="keyword">if</span> child &gt;= hi &#123; <span class="comment">//超出范围</span></span><br><span class="line">			<span class="keyword">break</span></span><br><span class="line">		&#125;</span><br><span class="line">		<span class="comment">// child+1 &lt; hi 判断右儿子有没超限</span></span><br><span class="line">		<span class="comment">// 选出左右儿子中更大的</span></span><br><span class="line">		<span class="keyword">if</span> child+<span class="number">1</span> &lt; hi &amp;&amp; data.Less(first+child, first+child+<span class="number">1</span>) &#123;</span><br><span class="line">			child++</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="comment">//父结点比最大儿子节点都大就结束构造</span></span><br><span class="line">		<span class="keyword">if</span> !data.Less(first+root, first+child) &#123;</span><br><span class="line">			<span class="keyword">return</span></span><br><span class="line">		&#125;</span><br><span class="line">		<span class="comment">// 父结点比最大儿子小，父结点与该节点交换，</span></span><br><span class="line">                <span class="comment">//因为这个节点原来已经跟兄弟节点比较过，</span></span><br><span class="line">                <span class="comment">//所以这个节点就是最大的节点</span></span><br><span class="line">		data.Swap(first+root, first+child)</span><br><span class="line">		root = child</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h2 id="快速排序"><a href="#快速排序" class="headerlink" title="快速排序"></a>快速排序</h2><p>该 <code>quickSort</code> 函数的整体框架是快排：</p>
<p>当切片数据量较大时，使用快排把数据分割成两个子问题（<code>doPivot</code>），把较小规模的子问题进行递归，较大规模的子问题继续循环迭代，实现类似于函数调用的效果，如果迭代或递归的深度超过 <code>maxDepth</code>，则使用堆排序<strong>防止栈溢出</strong>；当切片数据量较小（&lt;= 12）时，采用希尔排序法。</p>
<p>这里涉及两个要点，确定深度和如何分区</p>
<h3 id="确定深度"><a href="#确定深度" class="headerlink" title="确定深度"></a>确定深度</h3><p>根据数据规模len(data),算出数据深度，确保堆栈深度最大在lg(n+1)防止栈溢出</p>
<figure class="highlight go"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">//  2*ceil(lg(n+1)).2*上取整lg(n+1)</span></span><br><span class="line"><span class="function"><span class="keyword">func</span> <span class="title">maxDepth</span><span class="params">(n <span class="keyword">int</span>)</span> <span class="title">int</span></span> &#123;</span><br><span class="line">   <span class="keyword">var</span> depth <span class="keyword">int</span></span><br><span class="line">   <span class="keyword">for</span> i := n; i &gt; <span class="number">0</span>; i &gt;&gt;= <span class="number">1</span> &#123;</span><br><span class="line">      depth++</span><br><span class="line">   &#125;</span><br><span class="line">   <span class="keyword">return</span> depth * <span class="number">2</span></span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h3 id="分区"><a href="#分区" class="headerlink" title="分区"></a>分区</h3><p>快速排序的核心代码是切片切分，即把切片根据选定的轴切分成两部分（不大于轴的部分，和大于轴的部分）。</p>
<p>了解快排的朋友可能知道，快排最坏时间复杂度是 <code>O(n**2)</code>。最坏情况是每次切分的切片极不均衡，可能全是大于轴的部分，也可能全是不大于轴的部分。所以选择合适的轴是很必要的。</p>
<p><code>doPivot</code> 在切分之前，先使用 <code>medianOfThree</code> 函数选择一个肯定不是最大和最小的值作为轴pivot，放在了切片首位。然后把<strong>不大于</strong> <code>data[pivot]</code> 的数据放在了 <code>[lo, b)</code> 区间，把<strong>大于</strong> <code>data[pivot]</code> 的数据放在了 <code>(c, hi-1]</code> 区间（其中 <code>data[hi-1] &gt;= data[pivot]</code>）。</p>
<p>之后，该算法又估算了等于 <code>data[pivot]</code> 的数量，如果数量过多，则把与 <code>data[pivot]</code> 相等的数据放到了中间部分 区间为<code>(b, c-1)</code>。最后把 <code>data[pivot]</code> 交换到了 <code>b-1</code> 的位置。</p>
<p>至此，数据被切分成三个区间。</p>
<p><code>data[lo, b-1)</code>   小于 data[pivot]</p>
<p><code>data[b-1, c)</code>    等于 data[pivot]</p>
<p><code>data[c, hi)</code>      大于 data[pivot]</p>
<figure class="highlight go"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br><span class="line">96</span><br><span class="line">97</span><br><span class="line">98</span><br><span class="line">99</span><br><span class="line">100</span><br><span class="line">101</span><br><span class="line">102</span><br><span class="line">103</span><br><span class="line">104</span><br><span class="line">105</span><br><span class="line">106</span><br><span class="line">107</span><br><span class="line">108</span><br><span class="line">109</span><br><span class="line">110</span><br><span class="line">111</span><br><span class="line">112</span><br><span class="line">113</span><br><span class="line">114</span><br><span class="line">115</span><br><span class="line">116</span><br><span class="line">117</span><br><span class="line">118</span><br><span class="line">119</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">// 排序指定索引三个数，让他们换到合适的位置，中间索引m0存放最小的值</span></span><br><span class="line"><span class="function"><span class="keyword">func</span> <span class="title">medianOfThree</span><span class="params">(data Interface, m1, m0, m2 <span class="keyword">int</span>)</span></span> &#123;</span><br><span class="line">	<span class="comment">// m1 &lt; m0  =&gt; m0 m1</span></span><br><span class="line">	<span class="keyword">if</span> data.Less(m1, m0) &#123;</span><br><span class="line">		data.Swap(m1, m0)</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="comment">// 现在 data[m0] &lt;= data[m1] 继续比较</span></span><br><span class="line">	<span class="comment">// m2 &lt; m1 =&gt; m1 m2</span></span><br><span class="line">	<span class="keyword">if</span> data.Less(m2, m1) &#123;</span><br><span class="line">		data.Swap(m2, m1)</span><br><span class="line">		<span class="comment">// 现在 data[m0] &lt;= data[m2] &amp;&amp; data[m1] &lt; data[m2] data[m0]可能大于data[m1]，继续比较</span></span><br><span class="line">		<span class="keyword">if</span> data.Less(m1, m0) &#123;</span><br><span class="line">			data.Swap(m1, m0)</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="comment">// 现在 data[m0] &lt;= data[m1] &lt;= data[m2]</span></span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">func</span> <span class="title">doPivot</span><span class="params">(data Interface, lo, hi <span class="keyword">int</span>)</span> <span class="params">(midlo, midhi <span class="keyword">int</span>)</span></span> &#123;</span><br><span class="line">   <span class="comment">// 以下代码把数组分成前中后三段，如果数据够大，再各自分成前中后三段共九段</span></span><br><span class="line">   <span class="comment">// 通过三数处理lo索引处肯定不是最大和最小的值</span></span><br><span class="line">   <span class="comment">//start</span></span><br><span class="line">   m := <span class="keyword">int</span>(<span class="keyword">uint</span>(lo+hi) &gt;&gt; <span class="number">1</span>) <span class="comment">// 首先用位运算的方式求中间点，防止溢出</span></span><br><span class="line">   <span class="keyword">if</span> hi-lo &gt; <span class="number">40</span> &#123;</span><br><span class="line">      <span class="comment">//</span></span><br><span class="line">      <span class="comment">// Tukey's ``Ninther,'' median of three medians of three.</span></span><br><span class="line">      s := (hi - lo) / <span class="number">8</span></span><br><span class="line">      medianOfThree(data, lo, lo+s, lo+<span class="number">2</span>*s)</span><br><span class="line">      medianOfThree(data, m, m-s, m+s)</span><br><span class="line">      medianOfThree(data, hi<span class="number">-1</span>, hi<span class="number">-1</span>-s, hi<span class="number">-1</span><span class="number">-2</span>*s)</span><br><span class="line">   &#125;</span><br><span class="line">   medianOfThree(data, lo, m, hi<span class="number">-1</span>)</span><br><span class="line">   <span class="comment">//end</span></span><br><span class="line"></span><br><span class="line">   <span class="comment">//  以下代码实现</span></span><br><span class="line">   <span class="comment">//  为简洁表达以下pivot都代表data[pivot]</span></span><br><span class="line">   <span class="comment">//  data[lo] = pivot (set up by ChoosePivot)</span></span><br><span class="line">   <span class="comment">//  data[lo &lt; i &lt; a] &lt; pivot</span></span><br><span class="line">   <span class="comment">//  data[a &lt;= i &lt; b] &lt;= pivot</span></span><br><span class="line">   <span class="comment">//  data[b &lt;= i &lt; c] unexamined</span></span><br><span class="line">   <span class="comment">//  data[c &lt;= i &lt; hi-1] &gt; pivot</span></span><br><span class="line">   <span class="comment">//  data[hi-1] &gt;= pivot</span></span><br><span class="line">   pivot := lo</span><br><span class="line">   a, c := lo+<span class="number">1</span>, hi<span class="number">-1</span></span><br><span class="line"></span><br><span class="line">   <span class="comment">// 要么pivot是最大的，要么a&gt;=pivot</span></span><br><span class="line">   <span class="keyword">for</span> ; a &lt; c &amp;&amp; data.Less(a, pivot); a++ &#123; <span class="comment">// lo-a范围的数都 &lt; pivot</span></span><br><span class="line">   &#125;</span><br><span class="line">   b := a</span><br><span class="line">   <span class="keyword">for</span> &#123;</span><br><span class="line">      <span class="comment">// data[b] &lt;= pivot b++，因此左半区的数都&lt;=pivot</span></span><br><span class="line">      <span class="keyword">for</span> ; b &lt; c &amp;&amp; !data.Less(pivot, b); b++ &#123; </span><br><span class="line">      &#125;</span><br><span class="line">      <span class="comment">// data[c-1] &gt; pivot</span></span><br><span class="line">      <span class="keyword">for</span> ; b &lt; c &amp;&amp; data.Less(pivot, c<span class="number">-1</span>); c-- &#123; </span><br><span class="line">      &#125;</span><br><span class="line">      <span class="keyword">if</span> b &gt;= c &#123;</span><br><span class="line">         <span class="keyword">break</span></span><br><span class="line">      &#125;</span><br><span class="line">      <span class="comment">// data[b] &gt; pivot; data[c-1] &lt;= pivot</span></span><br><span class="line">      data.Swap(b, c<span class="number">-1</span>)</span><br><span class="line">      b++</span><br><span class="line">      c--</span><br><span class="line">   &#125;</span><br><span class="line">   <span class="comment">// 如果data[c &lt;= i &lt; hi-1] &gt; pivot，hi-c&lt;3 这表明数据中有重复的数，</span></span><br><span class="line">   <span class="comment">// 这里保守一些，认为hi-c&lt;5 为边界，如果重复的数较多，</span></span><br><span class="line">   <span class="comment">// 会以直接扫描跳过的方式把pivot左右两边的区间缩小</span></span><br><span class="line">   <span class="comment">// If hi-c&lt;3 then there are duplicates (by property of median of nine).</span></span><br><span class="line">   <span class="comment">// Let's be a bit more conservative, and set border to 5.</span></span><br><span class="line">   protect := hi-c &lt; <span class="number">5</span></span><br><span class="line">   <span class="keyword">if</span> !protect &amp;&amp; hi-c &lt; (hi-lo)/<span class="number">4</span> &#123; <span class="comment">//c就是下半区的位置，如果下半区数据太少，考虑重复数据太多</span></span><br><span class="line">      <span class="comment">// Lets test some points for equality to pivot</span></span><br><span class="line">      dups := <span class="number">0</span></span><br><span class="line">      <span class="keyword">if</span> !data.Less(pivot, hi<span class="number">-1</span>) &#123; <span class="comment">// data[hi-1] = pivot</span></span><br><span class="line">         data.Swap(c, hi<span class="number">-1</span>)</span><br><span class="line">         c++</span><br><span class="line">         dups++</span><br><span class="line">      &#125;</span><br><span class="line">      <span class="keyword">if</span> !data.Less(b<span class="number">-1</span>, pivot) &#123; <span class="comment">// data[b-1] = pivot</span></span><br><span class="line">         b--</span><br><span class="line">         dups++</span><br><span class="line">      &#125;</span><br><span class="line">      <span class="comment">// m-lo = (hi-lo)/2 &gt; 6</span></span><br><span class="line">      <span class="comment">// b-lo &gt; (hi-lo)*3/4-1 &gt; 8</span></span><br><span class="line">      <span class="comment">// ==&gt; m &lt; b ==&gt; data[m] &lt;= pivot</span></span><br><span class="line">      <span class="keyword">if</span> !data.Less(m, pivot) &#123; <span class="comment">// data[m] = pivot</span></span><br><span class="line">         data.Swap(m, b<span class="number">-1</span>)</span><br><span class="line">         b--</span><br><span class="line">         dups++</span><br><span class="line">      &#125;</span><br><span class="line">      <span class="comment">// if at least 2 points are equal to pivot, assume skewed distribution</span></span><br><span class="line">      <span class="comment">//如果测试到有太多相等的情况</span></span><br><span class="line">      protect = dups &gt; <span class="number">1</span></span><br><span class="line">   &#125;</span><br><span class="line">   <span class="comment">// 缩小边界，重新扫描上半区把，与pivot相等的数都放到中间位置</span></span><br><span class="line">   <span class="keyword">if</span> protect &#123;</span><br><span class="line">      <span class="comment">// Protect against a lot of duplicates</span></span><br><span class="line">      <span class="comment">// Add invariant:</span></span><br><span class="line">      <span class="comment">//  data[a &lt;= i &lt; b] unexamined</span></span><br><span class="line">      <span class="comment">//  data[b &lt;= i &lt; c] = pivot</span></span><br><span class="line">      <span class="keyword">for</span> &#123;</span><br><span class="line">         <span class="keyword">for</span> ; a &lt; b &amp;&amp; !data.Less(b<span class="number">-1</span>, pivot); b-- &#123; <span class="comment">// data[b] == pivot</span></span><br><span class="line">         &#125;</span><br><span class="line">         <span class="keyword">for</span> ; a &lt; b &amp;&amp; data.Less(a, pivot); a++ &#123; <span class="comment">// data[a] &lt; pivot</span></span><br><span class="line">         &#125;</span><br><span class="line">         <span class="keyword">if</span> a &gt;= b &#123;</span><br><span class="line">            <span class="keyword">break</span></span><br><span class="line">         &#125;</span><br><span class="line">         <span class="comment">// data[a] == pivot; data[b-1] &lt; pivot</span></span><br><span class="line">         data.Swap(a, b<span class="number">-1</span>)</span><br><span class="line">         a++</span><br><span class="line">         b--</span><br><span class="line">      &#125;</span><br><span class="line">   &#125;</span><br><span class="line">   <span class="comment">// Swap pivot into middle</span></span><br><span class="line">   data.Swap(pivot, b<span class="number">-1</span>)</span><br><span class="line">   <span class="keyword">return</span> b - <span class="number">1</span>, c</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h3 id="外层快排"><a href="#外层快排" class="headerlink" title="外层快排"></a>外层快排</h3><figure class="highlight go"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">func</span> <span class="title">quickSort</span><span class="params">(data Interface, a, b, maxDepth <span class="keyword">int</span>)</span></span> &#123;</span><br><span class="line">	<span class="keyword">for</span> b-a &gt; <span class="number">12</span> &#123; <span class="comment">// 数组元素还大于12时</span></span><br><span class="line">		<span class="comment">//栈深度最大在 lg(b-a).防止栈溢出</span></span><br><span class="line">		<span class="keyword">if</span> maxDepth == <span class="number">0</span> &#123; <span class="comment">//栈深度达到最大时使用堆排序</span></span><br><span class="line">			heapSort(data, a, b)</span><br><span class="line">			<span class="keyword">return</span></span><br><span class="line">		&#125;</span><br><span class="line">		maxDepth--</span><br><span class="line"></span><br><span class="line">		<span class="comment">//快排思想，按照合理的方法分成两个半区分别进行处理</span></span><br><span class="line">		mlo, mhi := doPivot(data, a, b)</span><br><span class="line">		<span class="keyword">if</span> mlo-a &lt; b-mhi &#123;</span><br><span class="line">			<span class="comment">// 前半区 mlo-a 元素较少直接递归</span></span><br><span class="line">			quickSort(data, a, mlo, maxDepth)</span><br><span class="line">			<span class="comment">// 递归完后，a=mhi 相当于处理后半区quickSort(data, mhi, b)，</span></span><br><span class="line">			<span class="comment">// 只是用循环来代替，减少了一次函数调用</span></span><br><span class="line">			a = mhi</span><br><span class="line"></span><br><span class="line">		&#125; <span class="keyword">else</span> &#123;</span><br><span class="line">			quickSort(data, mhi, b, maxDepth)</span><br><span class="line">			b = mlo <span class="comment">// 相当于 quickSort(data, a, mlo)</span></span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">if</span> b-a &gt; <span class="number">1</span> &#123;</span><br><span class="line">		<span class="comment">// 小于等于12个元素使用步长为 6，1的希尔排序</span></span><br><span class="line">		<span class="comment">// 步长为6 的排序</span></span><br><span class="line">		<span class="keyword">for</span> i := a + <span class="number">6</span>; i &lt; b; i++ &#123;</span><br><span class="line">			<span class="keyword">if</span> data.Less(i, i<span class="number">-6</span>) &#123; <span class="comment">//因为元素小于12，步长为6，一组最多只有两个元素，只用一个循环就可以</span></span><br><span class="line">				data.Swap(i, i<span class="number">-6</span>)</span><br><span class="line">			&#125;</span><br><span class="line">		&#125;</span><br><span class="line">		insertionSort(data, a, b) <span class="comment">//步长为1的，其实就是普通插入排序</span></span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h2 id="插入排序"><a href="#插入排序" class="headerlink" title="插入排序"></a>插入排序</h2><figure class="highlight go"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">// 只排序 a 到 b 的部分</span></span><br><span class="line"><span class="function"><span class="keyword">func</span> <span class="title">insertionSort</span><span class="params">(data Interface, a, b <span class="keyword">int</span>)</span></span> &#123;</span><br><span class="line">	<span class="keyword">for</span> i := a + <span class="number">1</span>; i &lt; b; i++ &#123;</span><br><span class="line">		<span class="comment">// 从后往前比较，遇到比新值大的就交换</span></span><br><span class="line">		<span class="comment">// a-i 之间已经是一个从小到大有序数组</span></span><br><span class="line">		<span class="comment">// 因此最好情况是已经排好序的数据，一个都不用交换,只要循环外层就好了o(n)</span></span><br><span class="line">		<span class="comment">// 最坏情况是一个排好逆序的数组，每次都要交换，o(n2)</span></span><br><span class="line">		<span class="keyword">for</span> j := i; j &gt; a &amp;&amp; data.Less(j, j<span class="number">-1</span>); j-- &#123;</span><br><span class="line">			<span class="comment">// 遇到后面大于等于前面就结束，已经排好序数组第一次就结束</span></span><br><span class="line">			<span class="comment">// 遇到后面比前面小就交换，一直换到合适位置</span></span><br><span class="line">			data.Swap(j, j<span class="number">-1</span>) <span class="comment">//交换j，j-1</span></span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h2 id="逆序排序"><a href="#逆序排序" class="headerlink" title="逆序排序"></a>逆序排序</h2><p>逆序排序数组，原来是从小到大，现在就是从大到小，实现很简单，就是把原来数组实现的Less覆盖了，调转了i,j的位置</p>
<figure class="highlight go"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">type</span> reverse <span class="keyword">struct</span> &#123;</span><br><span class="line">	Interface</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">func</span> <span class="params">(r reverse)</span> <span class="title">Less</span><span class="params">(i, j <span class="keyword">int</span>)</span> <span class="title">bool</span></span> &#123;</span><br><span class="line">	<span class="keyword">return</span> r.Interface.Less(j, i) <span class="comment">//覆盖原来的Less方法，i，j调转</span></span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">func</span> <span class="title">Reverse</span><span class="params">(data Interface)</span> <span class="title">Interface</span></span> &#123;</span><br><span class="line">	<span class="keyword">return</span> &amp;reverse&#123;data&#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h2 id="是否排序"><a href="#是否排序" class="headerlink" title="是否排序"></a>是否排序</h2><p>这个就更暴力了，直接遍历数组，如果遇到后面比前面小就返回false</p>
<figure class="highlight go"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">func</span> <span class="title">IsSorted</span><span class="params">(data Interface)</span> <span class="title">bool</span></span> &#123;</span><br><span class="line">	n := data.Len()</span><br><span class="line">	<span class="keyword">for</span> i := n - <span class="number">1</span>; i &gt; <span class="number">0</span>; i-- &#123;</span><br><span class="line">		<span class="keyword">if</span> data.Less(i, i<span class="number">-1</span>) &#123;</span><br><span class="line">			<span class="keyword">return</span> <span class="literal">false</span></span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">return</span> <span class="literal">true</span></span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h2 id="稳定算法-归并排序"><a href="#稳定算法-归并排序" class="headerlink" title="稳定算法-归并排序"></a>稳定算法-归并排序</h2><p>sort包里面的稳定算法主要用到<strong>归并排序</strong>，核心方法是<code>symMerge</code> 因为实在没看懂就先不写了，以后有机会再补充</p>
<figure class="highlight go"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">func</span> <span class="title">Stable</span><span class="params">(data Interface)</span></span> &#123;</span><br><span class="line">   stable(data, data.Len())</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">func</span> <span class="title">stable</span><span class="params">(data Interface, n <span class="keyword">int</span>)</span></span> &#123;</span><br><span class="line">   blockSize := <span class="number">20</span> <span class="comment">// 初始 blockSize 设置为 20</span></span><br><span class="line">   a, b := <span class="number">0</span>, blockSize</span><br><span class="line">   <span class="comment">// 对每个块（以及剩余不足blockSize的一个块）进行查询排序</span></span><br><span class="line">   <span class="keyword">for</span> b &lt;= n &#123;</span><br><span class="line">      insertionSort(data, a, b)</span><br><span class="line">      a = b</span><br><span class="line">      b += blockSize</span><br><span class="line">   &#125;</span><br><span class="line">   insertionSort(data, a, n)</span><br><span class="line"></span><br><span class="line">   <span class="keyword">for</span> blockSize &lt; n &#123;</span><br><span class="line">      a, b = <span class="number">0</span>, <span class="number">2</span>*blockSize</span><br><span class="line">      <span class="comment">// 每两个 blockSize 进行合并</span></span><br><span class="line">      <span class="keyword">for</span> b &lt;= n &#123;</span><br><span class="line">         symMerge(data, a, a+blockSize, b)</span><br><span class="line">         a = b</span><br><span class="line">         b += <span class="number">2</span> * blockSize</span><br><span class="line">      &#125;</span><br><span class="line">      <span class="comment">// 剩余一个多 blockSize 进行合并</span></span><br><span class="line">      <span class="keyword">if</span> m := a + blockSize; m &lt; n &#123;</span><br><span class="line">         symMerge(data, a, m, n)</span><br><span class="line">      &#125;</span><br><span class="line">      blockSize *= <span class="number">2</span></span><br><span class="line">   &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>





<h2 id="参考资料"><a href="#参考资料" class="headerlink" title="参考资料"></a>参考资料</h2><p><a href="https://blog.csdn.net/u014056175/article/details/100079748" target="_blank" rel="noopener">解释最难的Stable  symMerge</a></p>
<p><a href="https://segmentfault.com/a/1190000016514382" target="_blank" rel="noopener">【Go 源码分析】从 sort.go 看排序算法的工程实践</a></p>
<p><a href="https://studygolang.com/articles/26653" target="_blank" rel="noopener">Golang源码分析之sort</a></p>

        
<script src="/blog/js/qrious.min.js"></script>


        <hr>
        <div>
            
            <p>
                <span>专题: </span>
                
                <a href="/blog/series/#Golang学习">
                    <code key="Golang学习" class="post-label">Golang学习</code>
                </a>
                
            </p>
            
            <p>
                <span>本文发表于 2020-03-11，最后修改于 2020-03-12。</span>
            </p>
            <!-- 文章末尾的提示 start -->
            
            
            
                
            <!-- 文章末尾的提示 end -->
        </div>
        <hr />
        <p name="pagination" style="font-size: 1.2em">
    
    <a class="float-left" href="/blog/post/mysql-optimize-explain.html">上一篇 « EXPLAIN-执行计划查询命令</a>
    
    
</p>
    </article>
    <!-- 赞赏 -->
    <!--打赏-->

    <!-- 推荐阅读三篇文章 -->
    <div class="col-xs-12">
        <h3>推荐阅读</h3>
        
        <div class="post-preview">
    <div class="post-img" style="background-image: url('/blog/img/go.webp')"></div>
    <div class="post-info">
        <div class="post-info-center">
            <div class="hidden-xs">
                
                
                <span>/</span>
                
                <a class="text-gray" href="/blog/tags/#Golang"
                    title="Golang">Golang</a>
                <span>/</span>
                
                <a class="text-gray" href="/blog/tags/#Golang源码"
                    title="Golang源码">Golang源码</a>
                <span>/</span>
                
                
            </div>
            <a href="/blog/post/go-learn-lib-sorts.html" class="title">
                Go源码学习 sort包
            </a>
            <p class="text-gray">
                <small>
                    <span>发表于2020-03-11，</span>
                    <span class="hidden-xs">全文8862字，</span>
                    <span>阅读约30分钟</span>
                </small>
            </p>
        </div>
    </div>
</div>
        
        <div class="post-preview">
    <div class="post-img" style="background-image: url('/blog/img/database/database.webp')"></div>
    <div class="post-info">
        <div class="post-info-center">
            <div class="hidden-xs">
                
                
                <span>/</span>
                
                <a class="text-gray" href="/blog/tags/#MySQL"
                    title="MySQL">MySQL</a>
                <span>/</span>
                
                <a class="text-gray" href="/blog/tags/#MySQL优化"
                    title="MySQL优化">MySQL优化</a>
                <span>/</span>
                
                
            </div>
            <a href="/blog/post/mysql-optimize-explain.html" class="title">
                EXPLAIN-执行计划查询命令
            </a>
            <p class="text-gray">
                <small>
                    <span>发表于2020-03-03，</span>
                    <span class="hidden-xs">全文11409字，</span>
                    <span>阅读约39分钟</span>
                </small>
            </p>
        </div>
    </div>
</div>
        
        <div class="post-preview">
    <div class="post-img" style="background-image: url('/blog/img/goasm/1.webp')"></div>
    <div class="post-info">
        <div class="post-info-center">
            <div class="hidden-xs">
                
                
                <span>/</span>
                
                <a class="text-gray" href="/blog/tags/#Golang汇编"
                    title="Golang汇编">Golang汇编</a>
                <span>/</span>
                
                <a class="text-gray" href="/blog/tags/#Golang底层"
                    title="Golang底层">Golang底层</a>
                <span>/</span>
                
                <a class="text-gray" href="/blog/tags/#Golang"
                    title="Golang">Golang</a>
                <span>/</span>
                
                
            </div>
            <a href="/blog/post/go-asm-indroduce.html" class="title">
                Golang汇编(一)-Plan9介绍及指令详解
            </a>
            <p class="text-gray">
                <small>
                    <span>发表于2020-02-06，</span>
                    <span class="hidden-xs">全文9375字，</span>
                    <span>阅读约32分钟</span>
                </small>
            </p>
        </div>
    </div>
</div>
        
    </div>
    <div class="col-xs-12">
        <!-- 标签列表 -->
        <!-- Featured Tags -->
<style>
    #featured-tag .post-tag-item {
        font-size: 12px;
        line-height: 30px;
        display: inline-block;
        height: 30px;
        margin: 5px 0px;
        padding: 0 7px;
        color: #333;
        border-radius: 15px;
        background: #f6f6f6;
    }

    #featured-tag .post-tag-item:hover {
        color: #337ab7;
    }
</style>
<div id="featured-tag">
    
    <a class="post-tag-item" href="/blog/tags/#关于我" title="关于我"
        rel="1">#关于我 (1) </a>
    
    <a class="post-tag-item" href="/blog/tags/#友链" title="友链"
        rel="1">#友链 (1) </a>
    
    <a class="post-tag-item" href="/blog/tags/#Golang汇编" title="Golang汇编"
        rel="4">#Golang汇编 (4) </a>
    
    <a class="post-tag-item" href="/blog/tags/#Golang底层" title="Golang底层"
        rel="5">#Golang底层 (5) </a>
    
    <a class="post-tag-item" href="/blog/tags/#Golang" title="Golang"
        rel="8">#Golang (8) </a>
    
    <a class="post-tag-item" href="/blog/tags/#Golang基础" title="Golang基础"
        rel="1">#Golang基础 (1) </a>
    
    <a class="post-tag-item" href="/blog/tags/#Golang源码" title="Golang源码"
        rel="2">#Golang源码 (2) </a>
    
    <a class="post-tag-item" href="/blog/tags/#基础" title="基础"
        rel="2">#基础 (2) </a>
    
    <a class="post-tag-item" href="/blog/tags/#tcp/http" title="tcp/http"
        rel="2">#tcp/http (2) </a>
    
    <a class="post-tag-item" href="/blog/tags/#MySQL" title="MySQL"
        rel="3">#MySQL (3) </a>
    
    <a class="post-tag-item" href="/blog/tags/#MySQL优化" title="MySQL优化"
        rel="1">#MySQL优化 (1) </a>
    
</div>
    </div>
    <!-- 评论 -->
    <div class="col-xs-12">
        
    </div>
</div>
<aside class="float-left gkt-sidebar hidden-xs hidden-sm">
    <div style="clear: both"></div>
    <div class="gkt-sidebar-wrapper">
        <section class="box-shadow"><style>
    .gkt-summary {
        border: 1px solid #DDDDDD;
        border-radius: 3px;
        padding: 5px;
        width: 100%;
    }


    .gkt-summary nav {
        overflow: hidden;
    }

    .gkt-summary nav a {
        display: inline-block;
        text-align: center;
        color: #333;
        font-size: 12px;
    }

    .gkt-summary nav span {
        display: block;
    }

    .gkt-summary nav .middle {
        border-left: 1px solid #eaecef;
        border-right: 1px solid #eaecef;
    }

    .gkt-summary .number {
        font-weight: bold;
    }

    .gkt-summary .link-list {
        margin-top: 5px;
        margin-bottom: -5px;
        padding-top: 7px;
        border-top: 1px dashed #999;
        display: flex;
    }

    .gkt-summary .link-list a {
        flex: 1;
    }

    .gkt-summary .link-list img {
        width: 25px;
        height: 25px;
    }
</style>

<div class="gkt-summary">
    <nav>
        <a href="/blog/" class="col-xs-4">
            <number class="number">15</number><span>文章</span>
        </a>
        <a href="/blog/series" class="col-xs-4 middle">
            <number class="number">5</number><span>专题</span>
        </a>
        <a href="/blog/tags" class="col-xs-4">
            <number class="number">11</number><span>标签</span>
        </a>
    </nav>

    
    <div class="link-list">
        
        <a href="https://marvelthanos.com" target="_blank" rel="noopener"><img src="/blog/img/related_links/thanos.webp" /></a>
        
    </div>
    
</div></section>
        
        
        <section class="gkt-sidebar-content box-shadow">
            <strong>Golang学习</strong>
            <ul>
                
                <li>
                    <a href="/blog/post/go-learn-interface.html"
                        class="">Go学习 接口和类型断言</a>
                    
                </li>
                
                <li>
                    <a href="/blog/post/go-learn-lib-sorts.html"
                        class="gkt-sidebar-active">Go源码学习 sort包</a>
                    
                    <!-- Table of Contents -->
<div id="sidebar-toc">
  <!-- TOC  -->
  
  <ol class="toc-nav"><li class="toc-nav-item toc-nav-level-2"><a class="toc-nav-link" href="#接口"><span class="toc-nav-text">接口</span></a></li><li class="toc-nav-item toc-nav-level-2"><a class="toc-nav-link" href="#堆排序"><span class="toc-nav-text">堆排序</span></a></li><li class="toc-nav-item toc-nav-level-2"><a class="toc-nav-link" href="#快速排序"><span class="toc-nav-text">快速排序</span></a></li><li class="toc-nav-item toc-nav-level-2"><a class="toc-nav-link" href="#插入排序"><span class="toc-nav-text">插入排序</span></a></li><li class="toc-nav-item toc-nav-level-2"><a class="toc-nav-link" href="#逆序排序"><span class="toc-nav-text">逆序排序</span></a></li><li class="toc-nav-item toc-nav-level-2"><a class="toc-nav-link" href="#是否排序"><span class="toc-nav-text">是否排序</span></a></li><li class="toc-nav-item toc-nav-level-2"><a class="toc-nav-link" href="#稳定算法-归并排序"><span class="toc-nav-text">稳定算法-归并排序</span></a></li><li class="toc-nav-item toc-nav-level-2"><a class="toc-nav-link" href="#参考资料"><span class="toc-nav-text">参考资料</span></a></li></ol>
  
</div>

<script>
  (function () {
    var h2 = document.querySelectorAll('article h2');
    var h3 = document.querySelectorAll('article h3');
    var linkList = document.querySelectorAll('#sidebar-toc a');

    function findLinkElement(name) {
      for (var i = 0; i < linkList.length; i++) {
        var items = linkList[i].href.split('#');
        if (items && items[items.length - 1] === encodeURIComponent(name)) {
          return i;
        }
      }
      return -1;
    }

    function activeLink(titleList) {
      var scrollTop = document.documentElement.scrollTop || document.body.scrollTop;
      for (var i = titleList.length - 1; i >= 0; i--) {
        if (scrollTop - titleList[i].offsetTop > 0) {
          var index = findLinkElement(titleList[i].id);
          index != -1 && linkList[index].classList.add('gkt-sidebar-active');
          break;
        }
      }
    }

    window.addEventListener("scroll", function (e) {
      [].slice.call(linkList).forEach(function (link) {
        link.classList.remove('gkt-sidebar-active');
      })
      activeLink(h2);
    })
  })();
</script>
                    
                </li>
                
            </ul>
        </section>
        
        
        <section class="box-shadow">
            <strong>最近的文章</strong>
            <ul>
                
                <li>
                    <a href="/blog/post/go-learn-lib-sorts.html">Go源码学习 sort包</a>
                </li>
                
                <li>
                    <a href="/blog/post/mysql-optimize-explain.html">EXPLAIN-执行计划查询命令</a>
                </li>
                
                <li>
                    <a href="/blog/post/mysql-index-base.html">《高性能MySQL》笔记-索引基础</a>
                </li>
                
            </ul>
        </section>
        <section class="box-shadow text-center">
            
        </section>
    </div>
</aside>

<script>
    (function () {
        var ele = getDom('.gkt-sidebar-content')
        var wrapper = getDom('.gkt-sidebar-wrapper')
        var last = 0
        window.addEventListener("scroll", function (e) {
            var scrollTop = document.documentElement.scrollTop || document.body.scrollTop;
            var isDown = scrollTop > last;
            var pos = getPosition(ele).y - scrollTop;
            var downLimit = 50;
            var upLimit = -100;
            // uarrow.style.marginTop = scrollTop + 'px';
            isDown && pos <= downLimit && wrapper.classList.add("gkt-sidebar-fixed");
            !isDown && pos > upLimit && wrapper.classList.remove("gkt-sidebar-fixed");
            last = scrollTop
        })
    })();
    (function () {
        function resizeUArrow() {
            var s = getDom('.u-arrow-wrapper').style
            var pc = getDom('.post-container')
            s.left = getPosition(pc).x + 'px';
            s.width = pc.clientWidth + 'px';
        }
        resizeUArrow()
        window.addEventListener('resize', resizeUArrow);
    })();
</script>

    
</main>
    </div>
    <style>
    img#go-top {
        position: fixed;
        bottom: 100px;
        width: 50px;
        cursor: pointer;
        z-index: 9999;
    }
</style>
<img id="go-top" src="/blog/icon/top.png" class="hidden-xs" style="display: none" />
<script>
    (function () {
        var goTop = document.getElementById('go-top');
        var mainContainer = document.querySelector('.main-container');
        
        goTop.addEventListener('click', function () {
            window.scroll(0, 0);
        }, false);
        window.addEventListener('scroll', function () {
            var right = document.body.offsetWidth - mainContainer.getBoundingClientRect().right;
            var scrollTop = document.documentElement.scrollTop || document.body.scrollTop;
            goTop.style.right = right + 10 + 'px'
            scrollTop > 700 && (goTop.style.display = "block");
            scrollTop <= 700 && (goTop.style.display = "none");
        });
    })();
</script>
    <style>
    #geektutu-click-img-container {
        position: fixed;
        left: 0;
        top: 0;
        text-align: center;
        width: 100%;
        display: none;
        z-index: 9999;
    }

    #geektutu-click-img-container img {
        object-fit: contain;
        background: #eaecef;
        padding: 15px;
        border-radius: 10px;
        height: auto;
        width: auto;
        vertical-align: middle;
    }
</style>


<div id="geektutu-click-img-container">
    <img src="" alt="Big Image">
</div>

<script>
    (function () {
        var container = document.querySelector('#geektutu-click-img-container')
        var targetImg = container.querySelector('img')
        var imgs = document.querySelectorAll('article img');
        targetImg.addEventListener('click', function (e) {
            container.style.display = 'none';
            e && e.stopPropagation && e.stopPropagation();
        }, false);

        for (var i = 0; i < imgs.length; ++i) {
            var img = imgs[i];
            img.addEventListener('click', (function (src, rate) {
                return function (e) {
                    e && e.stopPropagation && e.stopPropagation();
                    if (window.innerWidth < 980) {
                        return
                    }
                    targetImg.style.height = targetImg.style.width = 'auto';
                    if (window.innerWidth / window.innerHeight > rate) {
                        targetImg.style.height = (window.innerHeight - 20) + 'px';
                    } else {
                        targetImg.style.width = (window.innerWidth - 20) + 'px';
                    }
                    container.style.height = window.innerHeight + 'px'
                    container.style.lineHeight = window.innerHeight + 'px'
                    container.style.display = 'block';
                    targetImg.src = src;
                };
            }(img.src, img.width / img.height)), false)
        }
    })();
</script>
    <!-- Footer -->
    <!-- Footer -->
<style>
    footer {
        width: 100%;
        line-height: 1.5;
        padding: 20px;
    }

    footer a {
        color: #333;
        text-decoration: none;
    }

    .footer-hexo img {
        height: 20px;
        margin-bottom: -5px;
    }

    .footer-hexo a {
        color: #337ab7;
    }
</style>
<footer class="text-center col-xs-12">
    <p>
        <small>© 2020 - Evrn - </small>
        <small>
            <a target="_blank" rel="nofollow noopener" href="http://www.miitbeian.gov.cn/"></a>
        </small>
    </p>
    <p class="footer-hexo">
        <!-- 但若直接使用或修改主题，请务必保留这段声明 -->
        <small>Powered by <a target="_blank" href="https://hexo.io">Hexo</a> | Theme
            <a target="_blank" href="https://geektutu.com">Geektutu</a>
            <a href="https://github.com/geektutu/hexo-theme-geektutu" target="_blank" rel="noopener">
                <img src=""
                    alt="Github Star">
            </a>
        </small>
    </p>
    
    <p>
        <small>
            <span id="busuanzi_container_site_pv">👁<span id="busuanzi_value_site_pv"></span></span> &nbsp;
            <span id="busuanzi_container_page_pv">📚<span id="busuanzi_value_page_pv"></span></span>
        </small>
    </p>
    
    

</footer>


<script>
    window.addEventListener('load', function () {
        globalAddScript('//busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js');
    })
</script>

<!-- Baidu Tongji -->





    <script>
        // 非本站网址，新开tab页签
        (function () {
            var stopBubble = function (e) {
                e && e.stopPropagation && e.stopPropagation();
            }
            var links = document.querySelectorAll('a');
            [].slice.call(links).forEach(function (item) {
                if (item.href && item.href.indexOf(window.location.host) === -1) {
                    item.target = '_blank'
                }
                // 阻止冒泡，不触发彩蛋。
                item.addEventListener('click', stopBubble, false);
            });
            var article = document.querySelector('article');
            article && article.addEventListener('click', stopBubble, false)
        })();
    </script>
    
</body>

</html>